package com.example.suanfademo;

/**
 * 美团面试  合并两个链表   https://www.xiaohongshu.com/discovery/item/68aec41e000000001c009621
 */
public class MergeTwoLists {
    class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    // 创建链表工具方法
    public  ListNode createLinkedList(int[] values) {
        if (values == null || values.length == 0) {
            return null;
        }

        ListNode dummy = new ListNode(-1);
        ListNode current = dummy;

        for (int value : values) {
            current.next = new ListNode(value);
            current = current.next;
        }

        return dummy.next;
    }
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 创建哑节点，简化操作
        ListNode dummy = new ListNode(-1);
        ListNode current = dummy;

        // 遍历两个链表，比较节点值
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                current.next = list1;
                list1 = list1.next;
            } else {
                current.next = list2;
                list2 = list2.next;
            }
            current = current.next;
        }

        // 将剩余部分直接连接到结果链表
        current.next = (list1 != null) ? list1 : list2;

        return dummy.next;
    }
    public static void main(String[] args) {
        MergeTwoLists mergeTwoLists = new MergeTwoLists();

        // 测试用例1：正常情况
        System.out.println("=== 测试用例1 ===");
        ListNode list1 = mergeTwoLists.createLinkedList(new int[]{1, 3, 5});
        ListNode list2 = mergeTwoLists.createLinkedList(new int[]{2, 4, 6});
        mergeTwoLists.mergeTwoLists(list1, list2);
    }

}
